# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=23
    
    PROBLEM
    
    A perfect number is a number for which the sum of its proper divisors is
    exactly equal to the number. For example, the sum of the proper divisors of
    28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect
    number.

    A number n is called deficient if the sum of its proper divisors is less
    than n and it is called abundant if this sum exceeds n.

    As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest
    number that can be written as the sum of two abundant numbers is 24. By
    mathematical analysis, it can be shown that all integers greater than 28123
    can be written as the sum of two abundant numbers. However, this upper
    limit cannot be reduced any further by analysis even though it is known
    that the greatest number that cannot be expressed as the sum of two
    abundant numbers is less than this limit.

    Find the sum of all the positive integers which cannot be written as the
    sum of two abundant numbers.

    
    NOTES
    
    
    REFERENCES
    
    
    PERFORMANCE
    ANALYTICAL time <function solution at 0x7f28b42c2758>: 71.859370 s
    PRACTICAL time <function solution at 0x7f9c2e268758>:  35.614834 s
    
"""
#
# Import
#
import time


#
# Globals / Constants
#
ANALYTICAL_MAX_NON_ABUNDANT_LIMIT = 28124
PRACTICAL_MAX_NON_ABUNDANT_LIMIT = 20161
MIN_ABUNDANT_SUM_NUMBER = 24
DEFICIENT = -1
PERFECT = 0
ABUNDANT = 1

def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected, message=""):
    message_f = "value %s != expected %s"
    message_f = message == "" and message_f or message_f + " (%s)"
    assert value == expected, message_f % (value, expected, message)


#
# Test Case / Solution
#
@timeit    
def test_case():
    # test 1: evaluation examples
    cases = [
        # number, divisiors, type
        (28, [1, 2, 4, 7, 14], PERFECT),
        (12, [1, 2, 3, 4, 6], ABUNDANT),
    ]
    
    for number, expected_divisors, expected_type in cases:
        proper_divisors = get_proper_divisors(number)
        type_ = evaluate_number(number)
        assert_match(proper_divisors, expected_divisors)
        assert_match(type_, expected_type)
        
    # test 2: distribution of types
    distribution = {
        DEFICIENT : 0,
        PERFECT : 0,
        ABUNDANT : 0
    }
    abundant_numbers = []
    perfect_numbers = []
    
    for number in xrange(1, ANALYTICAL_MAX_NON_ABUNDANT_LIMIT):
        type_ = evaluate_number(number)       
        distribution[type_] += 1
        if type_ == PERFECT:
            perfect_numbers.append(number)
        elif type_ == ABUNDANT:
            abundant_numbers.append(number)
        
    print distribution
    print "perfect numbers:", perfect_numbers
    
    # test 3: is sum of two abundant numbers?    
    cases = [
        # number, non-abundant sum
        (12, False),
        (24, True),
        (35, False),
        (36, True),
        (37, False),
        (60, True),
        (71, False),
        (28124, True)
    ]
    
    for number, expected in cases:
        is_sum = is_sum_of_two_abundant_numbers(number, abundant_numbers)
        assert_match(is_sum, expected, number)    

    print "test case passed!"

@timeit
def solution():
    """Find the sum of all the positive integers which cannot be written as
    the sum of two abundant numbers."""
    return sum(get_non_abundant_sum_numbers())
        


#
# Solution Code
#
def get_non_abundant_sum_numbers():
    non_abundant_sum_nums = []
    abundant_numbers = []
    
    for number in xrange(1, PRACTICAL_MAX_NON_ABUNDANT_LIMIT+1):
        type_ = evaluate_number(number)
        if type_ == ABUNDANT:
            abundant_numbers.append(number)
        
        if not is_sum_of_two_abundant_numbers(number, abundant_numbers):
            #print number, False
            non_abundant_sum_nums.append(number)
            
    return non_abundant_sum_nums

def evaluate_number(number):
    """returns number as deficient, perfect, or abundant"""
    proper_divisors = get_proper_divisors(number)
    divisor_sum = sum(proper_divisors)
    
    if divisor_sum < number:
        return DEFICIENT
    elif divisor_sum == number:
        return PERFECT
    else:
        return ABUNDANT

def is_abundant(number):
    return evaluate(number) == ABUNDANT
    
def is_sum_of_two_abundant_numbers(number, abundant_number_list):
    """return positive integers which cannot be written as the sum of two
    abundant numbers"""    
    if number < MIN_ABUNDANT_SUM_NUMBER:
        return False
    elif number > PRACTICAL_MAX_NON_ABUNDANT_LIMIT:
        return True
    
    abundant_predecessors = [n for n in abundant_number_list if n < number]

    while abundant_predecessors:
        n1 = abundant_predecessors[0]
        n2_list = reversed(abundant_predecessors)
        
        for n2 in n2_list:
            if n1 + n2 > number:
                abundant_predecessors.pop()
            elif n1 + n2 < number:
                break
            else:
                return True
        
        abundant_predecessors = abundant_predecessors[1:]
    
    return False

def get_proper_divisors(number):
    proper_divisors = [1]
    divisor_limit = int(round(number**0.5)) + 1
    
    for n in xrange(2, divisor_limit):
        if number % n == 0:
            proper_divisors += [n, number/n]
            
    return sorted(list(set(proper_divisors)))

    

#
# Additional Tests
#



#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    